package com.breeze.leetcode;

/**
 * https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
 * 167. 两数之和 II - 输入有序数组
 */
public class LeetCode167 {
    /**
     * 方法1:性能过低
     */
    public int[] twoSum(int[] numbers, int target) {
        int[] res = new int[2];
        for (int i = 0; i < numbers.length; i++) {
            int a = numbers[i];
            int temp = target - a;
            for (int j = i + 1; j < numbers.length && numbers[j] <= temp; j++) {
                if (numbers[j] == temp) {
                    res[0] = i + 1;
                    res[1] = j + 1;
                    return res;
                }
            }
        }
        return null;
    }

    /**
     * 方法2：找另一个数时通过二分法查找
     * 时间复杂度：O（nlog(n))
     * 空间复杂度：O（1）
     */
    public int[] twoSum1(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            int left = i + 1, right = numbers.length - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (numbers[mid] == target - numbers[i]) {
                    return new int[]{i + 1, mid + 1};
                } else if (numbers[mid] > target - numbers[i]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return new int[]{-1, -1};
    }

    /**
     * 方法3 双指针
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    public int[] twoSum2(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left + 1, right + 1};
            } else if (sum > target) {
                right--;
            } else {
                left++;
            }
        }
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        LeetCode167 leetCode167 = new LeetCode167();
        int[] nums = {2, 3, 4, 6, 8, 11, 15};
        int[] res = leetCode167.twoSum2(nums, 9);
        for (int re : res) {
            System.out.print(re + ",");
        }
    }
}
